package com.example.demo.LeetCode.arr;

/**
 * 二分法 查找
 * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
 */
public class DichotomySearch {
    /**
     * 解法1：左闭右闭
     * @param args
     */
    public static void main(String[] args) {
        int target = 4;
        int arr[] = {1,2,3,5,6,7,8,9,10};
        int left =0,right = arr.length-1;
        //左闭右闭区间
        while (left <= right){
            int middle = left+ ((right - left )/2);
            if (arr[middle] == target){
                System.out.println(middle);
                return;
            }
            // 数据在左边
            if (arr[middle] > target){
                right = middle -1;
            }else{
                left = middle + 1;
            }
        }
    }

    /**
     * 查找区间
     * 左闭右开
     * @param nums
     * @param target
     * @return
     */
    public  int solution(int[] nums ,int target){
        int left = 0,right = nums.length-1;
        while (left < right){
            int middle = left + (right - left) /2;
            if (nums[middle] == target){
                return middle;
            }
            if (nums[middle] > target){
                right = middle;
            }else {
                left = middle + 1;
            }
        }
        return -1;
    }
}
